{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Get Equal Substrings Within Budget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equalSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #尽可能使字符串相等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度相同的字符串，<code>s</code> 和 <code>t</code>。</p>\n",
    "\n",
    "<p>将 <code>s</code> 中的第 <code>i</code> 个字符变到 <code>t</code> 中的第 <code>i</code> 个字符需要 <code>|s[i] - t[i]|</code> 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。</p>\n",
    "\n",
    "<p>用于变更字符串的最大预算是 <code>maxCost</code>。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。</p>\n",
    "\n",
    "<p>如果你可以将 <code>s</code> 的子字符串转化为它在 <code>t</code> 中对应的子字符串，则返回可以转化的最大长度。</p>\n",
    "\n",
    "<p>如果 <code>s</code> 中没有子字符串可以转化成 <code>t</code> 中对应的子字符串，则返回 <code>0</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", t = \"bcdf\", maxCost = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>s<strong> </strong>中的<strong> </strong>\"abc\" 可以变为 \"bcd\"。开销为 3，所以最大长度为 3。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", t = \"cdef\", maxCost = 3\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为<code> 1。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", t = \"acde\", maxCost = 0\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length, t.length <= 10^5</code></li>\n",
    "\t<li><code>0 <= maxCost <= 10^6</code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 都只含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [get-equal-substrings-within-budget](https://leetcode.cn/problems/get-equal-substrings-within-budget/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [get-equal-substrings-within-budget](https://leetcode.cn/problems/get-equal-substrings-within-budget/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"\\n\"bcdf\"\\n3', '\"abcd\"\\n\"cdef\"\\n3', '\"abcd\"\\n\"acde\"\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        prefix = [0] + list(accumulate(abs(ord(a) - ord(b)) for a, b in zip(s, t)))\n",
    "\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r in range(1, len(prefix)):\n",
    "            while prefix[r] - prefix[l] > maxCost:\n",
    "                l += 1\n",
    "            ans = max(ans, r - l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        # s  =  'abcd'\n",
    "        # t  =  'bcdf'\n",
    "        # maxCost = 3\n",
    "        # windows_condition = maxCost\n",
    "\n",
    "        res, j, cost = 0, 0, 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != t[i]: cost += abs(ord(s[i]) - ord(t[i]))\n",
    "            while cost > maxCost:\n",
    "                cost -= abs(ord(s[j]) - ord(t[j]))\n",
    "                j += 1\n",
    "            res = max(res, i + 1 - j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        ret=0\n",
    "        l=r=0\n",
    "        cost=0\n",
    "        rec=0\n",
    "        while r<len(s):\n",
    "            cost+=abs(ord(s[r])-ord(t[r]))\n",
    "            rec+=1\n",
    "            while cost>maxCost:\n",
    "                cost-=abs(ord(s[l])-ord(t[l]))\n",
    "                l+=1\n",
    "                rec-=1\n",
    "            ret=max(ret,rec)\n",
    "            r+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        lenght = len(s)\n",
    "\n",
    "        cost = 0\n",
    "        res = 0\n",
    "        for right in range(lenght):\n",
    "            cost += abs(ord(s[right]) - ord(t[right]))\n",
    "            while cost > maxCost:\n",
    "                cost -= abs(ord(s[left]) - ord(t[left]))\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        cost = 0\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            cost += abs(ord(s[right]) - ord(t[right]))\n",
    "            if cost > maxCost:\n",
    "                cost -= abs(ord(s[left]) - ord(t[left]))\n",
    "                left += 1\n",
    "        return right - left + 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # cost = 0\n",
    "        # left = 0\n",
    "        # for right in range(len(s)):\n",
    "        #     cost += abs(ord(s[right]) - ord(t[right]))\n",
    "        #     if cost > maxCost:\n",
    "        #         cost -= abs(ord(s[left]) - ord(t[left]))\n",
    "        #         left += 1\n",
    "        # return right - left + 1\n",
    "\n",
    "\n",
    "        # count = 0\n",
    "        # left = 0\n",
    "        # for right in range(len(s)):\n",
    "        #     count += abs(ord(s[right]) - ord(t[right]))\n",
    "\n",
    "        #     if count > maxCost:\n",
    "        #         count -= abs(ord(s[left]) - ord(t[left]))\n",
    "        #         left += 1\n",
    "        # return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        cost = 0\n",
    "        optium = 0\n",
    "        left, right = 0, 0\n",
    "        while right < len(s):\n",
    "            while right < len(s):\n",
    "                cost += abs(ord(s[right]) - ord(t[right]))\n",
    "                right += 1\n",
    "                if cost > maxCost:\n",
    "                    break\n",
    "                else:\n",
    "                    optium = max(optium, right - left)\n",
    "            if right == len(s):\n",
    "                break\n",
    "            while left < right:\n",
    "                cost -= abs(ord(s[left]) - ord(t[left]))\n",
    "                left += 1\n",
    "                if cost <= maxCost:\n",
    "                    break\n",
    "\n",
    "        return optium"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        diff = [0]*len(s)\n",
    "        begin = 0\n",
    "        cur_cost = 0\n",
    "        path = 0\n",
    "        for i in range(len(s)):\n",
    "            diff[i] = abs(ord(s[i]) - ord(t[i]))\n",
    "            cur_cost = cur_cost + diff[i]\n",
    "            if cur_cost == maxCost:\n",
    "                if (i - begin + 1) > path:\n",
    "                    path = i - begin + 1\n",
    "            if cur_cost > maxCost:\n",
    "                if (i - begin) > path:\n",
    "                    path = i - begin\n",
    "                while cur_cost > maxCost:\n",
    "                    cur_cost = cur_cost - diff[begin]\n",
    "                    begin = begin + 1\n",
    "        if (i - begin + 1) > path:\n",
    "            path = i - begin +1\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "count = 0\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        distances = list()\n",
    "        for i in range(len(s)):\n",
    "            distances.append(abs(ord(s[i]) - ord(t[i])))\n",
    "        # print(distances)\n",
    "\n",
    "        stack = list()\n",
    "        max_len = 0\n",
    "        sum_v, cur_len = 0, 0\n",
    "        for ele in distances:\n",
    "            stack.append(ele)\n",
    "            sum_v += ele\n",
    "            cur_len += 1\n",
    "            if sum_v <= maxCost:\n",
    "                continue\n",
    "            else:\n",
    "                discard = stack.pop(0)\n",
    "                sum_v -= discard\n",
    "                cur_len -= 1\n",
    "                max_len = max(max_len, cur_len)\n",
    "        \n",
    "        return max(max_len, cur_len)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        l, r, N = 0, 0, min(len(s), len(t))\n",
    "        ret, costs = 0, 0\n",
    "        while r < N:\n",
    "            costs += abs(ord(s[r]) - ord(t[r]))\n",
    "            r += 1\n",
    "            while costs > maxCost:\n",
    "                costs -= abs(ord(s[l]) - ord(t[l]))\n",
    "                l += 1\n",
    "            # print(r, l, costs)\n",
    "            ret = max(ret, r - l)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        res, i, j = 0, 0, 0\n",
    "        n = len(s)\n",
    "        while i < n:\n",
    "            temp = abs(ord(s[i]) - ord(t[i]))\n",
    "            if maxCost >= temp:\n",
    "                maxCost -= temp\n",
    "            else:\n",
    "                while j < i and maxCost < temp:\n",
    "                    maxCost += abs(ord(s[j]) - ord(t[j]))\n",
    "                    j += 1\n",
    "                if maxCost >= temp:\n",
    "                    maxCost -= temp\n",
    "                else:\n",
    "                    i += 1\n",
    "                    j = i\n",
    "                    continue\n",
    "            res = max(res, i - j + 1)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        left=0\n",
    "        cost=0\n",
    "        maxlen=0\n",
    "        #先初始化三个值，作为\n",
    "        for right in range(len(s)):\n",
    "            gap=abs(ord(s[right])-ord(t[right]))\n",
    "            cost+=gap\n",
    "            while cost>maxCost:\n",
    "                cost-=abs(ord(s[left])-ord(t[left]))\n",
    "                left+=1\n",
    "            maxlen=max(maxlen,right-left+1)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        max_len,cur_cost=0,0\n",
    "        start=0\n",
    "        for end in range(len(s)):\n",
    "            cur_cost+=abs(ord(s[end])-ord(t[end]))\n",
    "            if cur_cost<=maxCost:\n",
    "                max_len=max(max_len,end-start+1)\n",
    "            while cur_cost>maxCost:\n",
    "                cur_cost-=abs(ord(s[start])-ord(t[start]))\n",
    "                start+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        max_len = 0\n",
    "        # maintain all the indexs of diff character within the slide window\n",
    "        diff_index = []\n",
    "        # the total cost of the slide window\n",
    "        total_cost = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        while r < len(t):\n",
    "            # no need to modified\n",
    "            if s[r] == t[r]:\n",
    "                r += 1\n",
    "            elif s[r] != t[r]:\n",
    "                curr_cost = abs(ord(s[r])-ord(t[r]))\n",
    "                # print(s[r], t[r], curr_cost)\n",
    "                total_cost += curr_cost\n",
    "                if total_cost <= maxCost:\n",
    "                    diff_index.append(r)\n",
    "                    r += 1\n",
    "                elif curr_cost > maxCost:\n",
    "                    max_len = max(max_len, r-l)\n",
    "                    r += 1\n",
    "                    l = r\n",
    "                    diff_index = []\n",
    "                    total_cost = 0\n",
    "                else:\n",
    "                    # print(s[:r], total_cost)\n",
    "                    # a possible sub answer\n",
    "                    max_len = max(max_len, r-l)\n",
    "                    diff_index.append(r)\n",
    "                    while total_cost > maxCost and len(diff_index) > 0:\n",
    "                        first_diff_index = diff_index.pop(0)\n",
    "                        total_cost -= abs(ord(s[first_diff_index]) - ord(t[first_diff_index]))\n",
    "                        l = first_diff_index + 1\n",
    "                    r += 1\n",
    "        max_len = max(max_len, r-l)\n",
    "        # print(s[l:r], t[l:r])\n",
    "        # cost = 0\n",
    "        # for i in range(l, r):\n",
    "        #     cost += abs(ord(s[i]) - ord(t[i]))\n",
    "        # print(cost)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        n = len(s)\n",
    "        diff = [0] * n\n",
    "        for i in range(n):\n",
    "            diff[i] = abs(ord(s[i]) - ord(t[i]))\n",
    "        l, r = 0, 0\n",
    "        sum= 0\n",
    "        maxl = 0\n",
    "        while r < n:\n",
    "            sum += diff[r]\n",
    "            while sum > maxCost:\n",
    "                sum -= diff[l]\n",
    "                l += 1\n",
    "            maxl = max(maxl, r - l + 1)\n",
    "            r += 1\n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        left = 0\n",
    "        n = len(s)\n",
    "        ret = 0\n",
    "        cur_len = 0\n",
    "        for i in range(n):\n",
    "            cur_cost = abs(ord(s[i]) - ord(t[i]))\n",
    "            if maxCost - cur_cost >= 0:\n",
    "                maxCost -= cur_cost\n",
    "                cur_len += 1\n",
    "            else:\n",
    "                while i > left and maxCost < cur_cost:\n",
    "                    maxCost += abs(ord(s[left]) - ord(t[left]))\n",
    "                    left += 1\n",
    "                    cur_len -= 1\n",
    "                if maxCost >= cur_cost:\n",
    "                    maxCost -= cur_cost\n",
    "                    cur_len += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "            ret = max(cur_len, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        l=r=res=cost=0\n",
    "        while r<len(s):\n",
    "            cost+=abs(ord(s[r])-ord(t[r]))\n",
    "            while cost>maxCost:\n",
    "                cost-=abs(ord(s[l])-ord(t[l]))\n",
    "                l+=1\n",
    "            res=max(res,r-l+1)\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        cur = 0\n",
    "        res = 0\n",
    "\n",
    "        while right < n:\n",
    "            cur += abs(ord(s[right]) - ord(t[right]))\n",
    "            \n",
    "            if cur <= maxCost:\n",
    "                print(left, right)\n",
    "                res = max(res, right - left + 1)\n",
    "            else:\n",
    "                while cur > maxCost:\n",
    "                    cur -= abs(ord(s[left]) - ord(t[left]))\n",
    "                    \n",
    "                    left += 1\n",
    "                    \n",
    "                res = max(res, right-left+1)\n",
    "                    \n",
    "                    \n",
    "            right += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        n = len(s)\n",
    "        costs = [0] * n\n",
    "        for i in range(n):\n",
    "            costs[i] = abs(ord(s[i]) - ord(t[i]))\n",
    "        left, right, sum_cost, res = 0, 0, 0, 0\n",
    "        while right < n:\n",
    "            sum_cost += costs[right]\n",
    "            while sum_cost > maxCost:\n",
    "                sum_cost -= costs[left]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        n = len(s)\n",
    "        start, end, total, res = 0, 0, 0, 0\n",
    "        record = [0] * n\n",
    "        for i in range(n):\n",
    "            record[i] = abs(ord(t[i]) - ord(s[i]))\n",
    "\n",
    "        for end in range(n):\n",
    "            total += record[end]\n",
    "            while total > maxCost:\n",
    "                res = max(res, end - start)\n",
    "                total -= record[start]\n",
    "                start += 1\n",
    "\n",
    "        res = max(res, end - start + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        diff = [abs(ord(i) - ord(j)) for (i,j) in zip(s,t)]\n",
    "        maxLen = l = r= 0\n",
    "        total = 0\n",
    "        n = len(s)\n",
    "        while r < n:\n",
    "            total += diff[r]\n",
    "            while total > maxCost:\n",
    "                total -= diff[l]\n",
    "                l += 1\n",
    "            maxLen = max(maxLen , r - l +1)\n",
    "            r += 1\n",
    "        return maxLen "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        lst = []\n",
    "        for x, y in zip(s, t):\n",
    "            lst.append(abs(ord(x) - ord(y)))\n",
    "        print(lst)\n",
    "        left, right, lens = 0, 0, len(lst)\n",
    "        sums = 0\n",
    "        res = 0\n",
    "        while right < lens:\n",
    "            # 求和\n",
    "            sums += lst[right]\n",
    "            # 不满足条件的情况下\n",
    "            while sums > maxCost and left <= right:\n",
    "                sums -= lst[left]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        dist = [abs(ord(t[i]) - ord(s[i])) for i in range(len(s))]\n",
    "        print(dist)\n",
    "        left, curr_cost, max_len, curr_len = 0, 0, 0, 0\n",
    "\n",
    "        for val in dist:\n",
    "            curr_cost += val\n",
    "            curr_len += 1\n",
    "            while curr_cost > maxCost:\n",
    "                curr_cost -= dist[left]\n",
    "                curr_len -= 1\n",
    "                left += 1\n",
    "            max_len = max(max_len, curr_len)\n",
    "            print(max_len)\n",
    "        \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        if not s or not t:\n",
    "            return 0\n",
    "\n",
    "        s_list = list(map(ord, list(s)))\n",
    "        t_list = list(map(ord, list(t)))\n",
    "\n",
    "        cost_list = [abs(s_list[i] - t_list[i]) for i in range(len(s_list))]\n",
    "\n",
    "        left = 0\n",
    "        cur_sum = 0\n",
    "        max_len = 0\n",
    "\n",
    "        for r in range(len(cost_list)):\n",
    "            while left <= r and cur_sum + cost_list[r] > maxCost:\n",
    "                cur_sum -= cost_list[left]\n",
    "                left += 1\n",
    "\n",
    "            max_len = max(r-left+1, max_len)\n",
    "            cur_sum += cost_list[r]\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        lists,listt = list(s),list(t)\n",
    "        diff = [abs(ord(listt[i]) - ord(lists[i])) for i in range(len(s))]\n",
    "        res = 0\n",
    "        sums = 0\n",
    "        left,right = 0,0\n",
    "        while right < len(s):\n",
    "            sums += diff[right]\n",
    "            while sums > maxCost:\n",
    "                sums -= diff[left]\n",
    "                left += 1\n",
    "            res = max(res,right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        s = list(map(ord, s))\n",
    "        t = list(map(ord, t))\n",
    "        d = [abs(x - y) for x, y in zip(s,t)]\n",
    "        N = len(d)\n",
    "        left = 0\n",
    "        cur_len = 0\n",
    "        max_len = 0\n",
    "        total_cost = 0\n",
    "        for i in range(N):\n",
    "            total_cost += d[i]\n",
    "            cur_len += 1\n",
    "            while total_cost > maxCost:\n",
    "                 total_cost -= d[left]\n",
    "                 left += 1\n",
    "                 cur_len -= 1\n",
    "            if cur_len > max_len:\n",
    "                max_len = cur_len\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        \"\"\"\n",
    "        二分法\n",
    "        cost = [0]\n",
    "        result = 0\n",
    "        for i in range(len(s)):\n",
    "            cost.append(cost[-1] + abs(ord(s[i])-ord(t[i])))\n",
    "        for i in range(len(cost)):\n",
    "            result = max(result,i - bisect.bisect_left(cost, cost[i] - maxCost))\n",
    "        return result\n",
    "        \"\"\"\n",
    "        #滑窗\n",
    "        sumCost = [0]\n",
    "        for i in range(len(s)):\n",
    "            sumCost.append(sumCost[-1] + abs(ord(s[i]) - ord(t[i])))\n",
    "        left = 0\n",
    "        right = 0\n",
    "        result = 0\n",
    "        total = 0\n",
    "        while right < len(sumCost):\n",
    "            total = sumCost[right] - sumCost[left]\n",
    "            while total > maxCost:\n",
    "                left += 1\n",
    "                total = sumCost[right] - sumCost[left]\n",
    "            result = max(result, right - left)\n",
    "            right += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        n = len(s)\n",
    "        gap = [abs(ord(s[i]) - ord(t[i])) for i in range(n)]\n",
    "        res = 0\n",
    "        subStr = set()\n",
    "        cur = 0\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if i - 1 in subStr:\n",
    "                subStr.remove(i - 1)\n",
    "                cur -= gap[i - 1]\n",
    "            j = max(i, j)\n",
    "            while cur <= maxCost and j < n:\n",
    "                if cur + gap[j] <= maxCost:\n",
    "                    cur += gap[j]\n",
    "                    subStr.add(j)\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            res = max(res, len(subStr))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        ord_s = [ord(c) for c in s]\n",
    "        ord_t = [ord(c) for c in t]\n",
    "        cost_t = [abs(ord_s[i] - ord_t[i]) for i in range(len(ord_s))]\n",
    "        print(cost_t)\n",
    "\n",
    "        curCost = 0\n",
    "        max_len = 0\n",
    "        temp_len = 0\n",
    "        sub_string = []\n",
    "        for i in range(len(ord_s)):\n",
    "            if cost_t[i] + curCost <= maxCost:\n",
    "                curCost += cost_t[i]\n",
    "                sub_string.append(cost_t[i])\n",
    "            else:\n",
    "                if cost_t[i] <= maxCost:\n",
    "                    while curCost + cost_t[i] > maxCost:\n",
    "                        old_cost = sub_string.pop(0)\n",
    "                        curCost -= old_cost\n",
    "                    sub_string.append(cost_t[i])\n",
    "                    curCost += cost_t[i]\n",
    "                else:\n",
    "                    sub_string = []\n",
    "                    curCost = 0\n",
    "            max_len = max(max_len, len(sub_string))\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        n= len(s)\n",
    "\n",
    "        sm = [0] * (1+n)\n",
    "\n",
    "        for i in range(n):\n",
    "            sm[i+1] = sm[i] + abs(ord(s[i]) - ord(t[i]))\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "\n",
    "        for r in range(n):\n",
    "            if sm[r+1] - sm[l] <= maxCost:\n",
    "                res = max(res, r - l+1)\n",
    "            while sm[r+1]-sm[l] > maxCost:\n",
    "                l += 1\n",
    "        # res = max(res, r-l+1)\n",
    "        return res\n",
    "        # while l < n and r+1 < n:\n",
    "\n",
    "        #     while r+1 < n and sm[r+1] - sm[l] <= maxCost:\n",
    "        #         r += 1\n",
    "        #     res = max(res, r - l)\n",
    "        #     if sm[r + 1] - sm[l] > maxCost:\n",
    "        #         l += 1\n",
    "        # res = max(res, r-l+1)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        ans = 0\n",
    "        dp = [0] + [abs(a - b) for (a, b) in zip([ord(c) for c in s], [ord(c) for c in t])]\n",
    "        n = len(dp)\n",
    "        for i in range(1, n):\n",
    "            dp[i] += dp[i-1]\n",
    "        for i in range(n):\n",
    "            j = i + ans\n",
    "            while j < n:\n",
    "                if dp[j] - dp[i] > maxCost:\n",
    "                    break\n",
    "                j += 1\n",
    "            ans = max(ans, j-i-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        nums = [0]\n",
    "        for x, y in zip(s, t):\n",
    "            nums.append(nums[-1] + abs(ord(y)-ord(x)))\n",
    "        res = 0\n",
    "        for right in range(len(s)):\n",
    "            left = bisect.bisect_left(nums, nums[right+1]-maxCost)\n",
    "            res = max(res, right-left+1)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:\n",
    "        lst = []\n",
    "        for i in range(len(s)):\n",
    "            lst.append(abs(ord(s[i]) - ord(t[i])))\n",
    "        l = [0] * (len(lst) + 1)\n",
    "        for i in range(1, len(lst) + 1):\n",
    "            l[i] = l[i-1] + lst[i-1]\n",
    "        maxL = 0\n",
    "        for i in range(1, len(l)):\n",
    "            start = bisect.bisect_left(l, l[i] - maxCost)\n",
    "            maxL = max(maxL, i - start)\n",
    "        return maxL"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
